package com.c2b.algorithm.leetcode.jzoffer.tree;

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/">二叉树中和为某一值的路径</a>
 * <p>给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点 是指没有子节点的节点。</p>
 * <pre>
 *                       5
 *                    /     \
 *                   4       8
 *                 /        /  \
 *               11       13    4
 *              / \            / \
 *             7   2          5   1
 *      输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 *      输出：[[5,4,11,2],[5,8,4,5]]
 * </pre>
 *
 * @author c2b
 * @since 2023/4/4 11:12
 */
public class JzOffer0034PathSum_M {

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        // 辅助map，用于记录当前节点与父节点的映射关系
        Map<TreeNode, TreeNode> currentNode2parentNodeMap = new HashMap<>();
        currentNode2parentNodeMap.put(root, null);
        // 辅助队列用于保存树中的节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode currentNode = queue.poll();
            // 先将左右子节点入队。同时维护映射map
            if (currentNode.left != null) {
                currentNode2parentNodeMap.put(currentNode.left, currentNode);
                queue.offer(currentNode.left);
            }
            if (currentNode.right != null) {
                currentNode2parentNodeMap.put(currentNode.right, currentNode);
                queue.offer(currentNode.right);
            }
            // 先判断当前节点的左右子节点是否都为null(即当前节点是否为叶子节点)
            if (currentNode.left == null && currentNode.right == null) {
                // 每弹出一个节点就去map中不断查找父节点，直到根节点，
                int tempVal = 0;
                List<Integer> list = new ArrayList<>();
                while (currentNode != null) {
                    list.add(currentNode.val);
                    tempVal += currentNode.val;
                    currentNode = currentNode2parentNodeMap.get(currentNode);
                }
                // 判断路径上所有节点值之和是否等于target
                if (tempVal == target) {
                    res.add(list);
                }
            }
        }
        for (List<Integer> integerList : res) {
            Collections.reverse(integerList);
        }
        return res;
    }


    public List<List<Integer>> pathSum2(TreeNode root, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        dfs(root, target, result, path);
        return result;
    }

    private void dfs(TreeNode root, int target, List<List<Integer>> result, Deque<Integer> path) {
        if (root == null) {
            return;
        }
        path.offerLast(root.val);
        target -= root.val;
        if (root.left == null && root.right == null && target == 0) {
            result.add(new LinkedList<>(path));
        }
        dfs(root.left, target, result, path);
        dfs(root.right, target, result, path);
        path.pollLast();
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(5);
        treeNode.left = new TreeNode(4);
        treeNode.right = new TreeNode(8);
        treeNode.left.left = new TreeNode(11);
        treeNode.right.left = new TreeNode(13);
        treeNode.right.right = new TreeNode(4);
        treeNode.left.left.left = new TreeNode(7);
        treeNode.left.left.right = new TreeNode(2);
        treeNode.right.right.left = new TreeNode(5);
        treeNode.right.right.right = new TreeNode(1);
        JzOffer0034PathSum_M jzOffer0034PathSum_m = new JzOffer0034PathSum_M();
        List<List<Integer>> lists = jzOffer0034PathSum_m.pathSum2(treeNode, 22);
        for (List<Integer> list : lists) {
            for (Integer integer : list) {
                System.out.print(integer + "  ");
            }
            System.out.println();
        }
    }
}
